# Tree in Data Structures - javatpoint
# https://www.javatpoint.com/tree
"""
Here are some conceptual definitions, properties, and operations related to trees:

1. Tree:
   - A tree is a non-linear hierarchical data structure consisting of nodes connected by edges.
   - It is a collection of entities (nodes) organized in a hierarchical manner.
   - In a tree, there is a unique node called the root that serves as the starting point.
   - The nodes in a tree are connected by directed edges, and each node (except the root) has exactly one parent and zero or more children.
   - Trees are often used to represent hierarchical relationships, such as organizational structures, file systems, and family trees.

2. Node:
   - A node is a fundamental building block of a tree.
   - Each node represents an entity in the tree and contains some associated data.
   - Nodes are connected by edges to form the hierarchical structure of the tree.

3. Root:
   - The root is the topmost node in a tree.
   - It is the starting point of the tree and has no parent.
   - Every tree has a single root node.

4. Parent and Child:
   - A parent is a node that has one or more children.
   - A child is a node that has a parent.

5. Leaf Node:
   - A leaf node, also known as a terminal node or external node, is a node that has no children.
   - It is the end point of a branch in the tree.

6. Internal Node:
   - An internal node, also known as a non-leaf node or branch node, is a node that has one or more children.
   - It is not a leaf node and serves as an intermediate node in the tree.

7. Depth:
   - The depth of a node in a tree is the length of the path from the root to that node.
   - The depth of the root node is 0.

8. Height:
   - The height of a tree is the length of the longest path from the root to a leaf node.
   - It represents the maximum number of edges between the root and any leaf node in the tree.

9. Size:
   - The size of a tree is the total number of nodes in the tree, including the root and all its descendants.

10. Traversal:
    - Tree traversal refers to the process of visiting and examining each node in a tree in a specific order.
    - Common tree traversal algorithms include depth-first traversal (e.g., pre-order, in-order, post-order) and breadth-first traversal.

11. Operations:
    - Adding a node: Add a new node to the tree as a child of an existing node.
    - Removing a node: Remove a node and its subtree from the tree.
    - Searching for a node: Find a specific node in the tree based on its value or other criteria.
    - Updating node data: Modify the data associated with a node.
    - Calculating depth and height: Determine the depth and height of a node or the entire tree.
    - Finding leaf nodes and branch nodes: Identify all the leaf nodes or branch nodes in the tree.
    - Tree representation: Generate a string or visual representation of the tree structure.

These definitions, properties, and operations provide a foundational understanding of trees and can be used to implement and work with tree data structures effectively.
"""
class TreeNode:
    """
    TreeNode represents a node in a tree.

    Attributes:
        data: Data stored in the node.
        children: List of child nodes.
    """

    def __init__(self, data=None):
        """
        Initialize a TreeNode with data and an empty list of children.

        Args:
            data: Initial data for this node. Defaults to None.
        """
        self.data = data
        self.children = []

    def add_child(self, child):
        """
        Add a child node to the current node.

        Args:
            child: Child node to be added.
        """
        self.children.append(child)

    def remove_child(self, child):
        """
        Remove a child node from the current node.

        Args:
            child: Child node to be removed.
        """
        self.children.remove(child)

    def is_leaf(self):
        """
        Check if the current node is a leaf node.

        Returns:
            True if the node is a leaf, False otherwise.
        """
        return len(self.children) == 0

    def is_internal(self):
        """
        Check if the current node is an internal node.

        Returns:
            True if the node is internal, False otherwise.
        """
        return len(self.children) > 0


class Tree:
    """
    Tree represents a tree data structure.

    Attributes:
        root: Root node of the tree.
    """

    def __init__(self):
        """
        Initialize an empty tree with no root node.
        """
        self.root = None

    def add_root(self, data):
        """
        Add a root node to the tree.

        Args:
            data: Data for the root node.
        """
        if self.root:
            raise Exception("Root node already exists")
        self.root = TreeNode(data)

    def add_child(self, parent, child_data):
        """
        Add a child node to a parent node.

        Args:
            parent: Parent node to which the child node will be added.
            child_data: Data for the child node.
        """
        if parent is None:
            raise Exception("Parent node does not exist")
        child = TreeNode(child_data)
        parent.add_child(child)

    def remove_node(self, node):
        """
        Remove a node from the tree.

        Args:
            node: Node to be removed.
        """
        if node is None:
            raise Exception("Node does not exist")

        if node == self.root:
            self.root = None
        else:
            parent = self._find_parent_node(self.root, node)
            if parent:
                parent.remove_child(node)
            else:
                raise Exception("Parent node not found")

    def _find_parent_node(self, start_node, node):
        """
        Helper method to find the parent node of a given node.

        Args:
            start_node: Node to start the search from.
            node: Node for which to find the parent.

        Returns:
            Parent node if found, None otherwise.
        """
        if start_node == node:
            return None

        for child in start_node.children:
            if child == node:
                return start_node
            else:
                parent = self._find_parent_node(child, node)
                if parent:
                    return parent

        return None

    def breadth_first_traversal(self):
        """
        Perform breadth-first traversal of the tree and print the node values.
        """
        if self.root is None:
            return
        queue = [self.root]
        while queue:
            node = queue.pop(0)
            print(node.data)
            queue.extend(node.children)

    def size(self):
        """
        Calculate the size (number of nodes) of the tree.

        Returns:
            Size of the tree.
        """
        return self._size_helper(self.root)

    def _size_helper(self, node):
        """
        Helper method for calculating the size of the tree.

        Args:
            node: Current node being visited.

        Returns:
            Size of the subtree rooted at the current node.
        """
        if node is None:
            return 0
        count = 1
        for child in node.children:
            count += self._size_helper(child)
        return count

    def height(self):
        """
        Calculate the height of the tree.

        Returns:
            Height of the tree.
        """
        return self._height_helper(self.root)

    def _height_helper(self, node):
        """
        Helper method for calculating the height of the tree.

        Args:
            node: Current node being visited.

        Returns:
            Height of the subtree rooted at the current node.
        """
        if node is None:
            return 0
        if not node.children:
            return 1
        heights = []
        for child in node.children:
            heights.append(self._height_helper(child))
        return max(heights) + 1

    def depth(self, node):
        """
        Calculate the depth of a node in the tree.

        Args:
            node: Node for which to calculate the depth.

        Returns:
            Depth of the node.
        """
        return self._depth_helper(self.root, node, 0)

    def _depth_helper(self, start_node, node, depth):
        """
        Helper method for calculating the depth of a node in the tree.

        Args:
            start_node: Current node being visited.
            node: Node for which to calculate the depth.
            depth: Current depth in the tree.

        Returns:
            Depth of the node if found, -1 otherwise.
        """
        if start_node == node:
            return depth

        for child in start_node.children:
            child_depth = self._depth_helper(child, node, depth + 1)
            if child_depth != -1:
                return child_depth

        return -1

    def subtree(self, node):
        """
        Create a new tree representing the subtree rooted at the given node.

        Args:
            node: Root node of the subtree.

        Returns:
            New tree representing the subtree.
        """
        subtree = Tree()
        subtree.root = node
        return subtree

    def leaves(self):
        """
        Get a list of leaf nodes in the tree.

        Returns:
            List of leaf nodes.
        """
        return self._leaves_helper(self.root)

    def _leaves_helper(self, node):
        """
        Helper method for getting a list of leaf nodes in the tree.

        Args:
            node: Current node being visited.

        Returns:
            List of leaf nodes.
        """
        if node is None:
            return []

        if node.is_leaf():
            return [node]

        leaves = []
        for child in node.children:
            leaves.extend(self._leaves_helper(child))
        return leaves

    def branches(self):
        """
        Get a list of branch nodes in the tree.

        Returns:
            List of branch nodes.
        """
        return self._branches_helper(self.root)

    def _branches_helper(self, node):
        """
        Helper method for getting a list of branch nodes in the tree.

        Args:
            node: Current node being visited.

        Returns:
            List of branch nodes.
        """
        if node is None:
            return []

        if node.is_internal():
            branches = [node]
        else:
            branches = []

        for child in node.children:
            branches.extend(self._branches_helper(child))
        return branches

    def pre_order(self):
        """
        Perform a pre-order traversal of the tree and print the node values.
        """
        if self.root is None:
            return
        self._pre_order_helper(self.root)

    def _pre_order_helper(self, node):
        """
        Helper method for pre-order traversal.

        Args:
            node: Current node being visited.
        """
        print(node.data)
        for child in node.children:
            self._pre_order_helper(child)

    def in_order(self):
        """
        Perform an in-order traversal of the tree and print the node values.
        """
        if self.root is None:
            return
        self._in_order_helper(self.root)

    def _in_order_helper(self, node):
        """
        Helper method for in-order traversal.

        Args:
            node: Current node being visited.
        """
        if node.is_leaf():
            print(node.data)
        else:
            for child in node.children:
                self._in_order_helper(child)

    def post_order(self):
        """
        Perform a post-order traversal of the tree and print the node values.
        """
        if self.root is None:
            return
        self._post_order_helper(self.root)

    def _post_order_helper(self, node):
        """
        Helper method for post-order traversal.

        Args:
            node: Current node being visited.
        """
        for child in node.children:
            self._post_order_helper(child)
        print(node.data)

    def is_internal_node(self, node):
        """
        Check if a given node is an internal node.

        Args:
            node: Node to check.

        Returns:
            True if the node is internal, False otherwise.
        """
        return node.is_internal()

    def __repr__(self):
        """
        Returns a string that represents a valid Python expression that could be used to recreate the tree.

        Returns:
            A string that represents a valid Python expression.
        """
        if self.root is None:
            return "Empty Tree"
        return f"Tree(depth={self.height()}, size={self.size()}, root={self.root.data})"

    def _display_helper(self, node):
        """
        Helper method for generating the string representation of the tree.

        Args:
            node: Current node being visited.

        Returns:
            List of strings representing the tree structure.
        """
        lines = []
        line = str(node.data)
        if not node.children:
            lines.append(line)
        else:
            child_lines = []
            for child in node.children:
                child_lines.extend(self._display_helper(child))
            lines.append(line)
            for i in range(len(child_lines)):
                if i == len(child_lines) - 1:
                    lines.append("└── " + child_lines[i])
                else:
                    lines.append("├── " + child_lines[i])
        return lines

    def _display(self):
        """
        Returns a string representation of the tree.

        Returns:
            String representation of the tree.
        """
        if self.root is None:
            return "Empty Tree"

        lines = self._display_helper(self.root)
        return "\n".join(lines)

    def __str__(self):
        """
        Returns a string representing the tree.

        Returns:
            A string representing the tree.
        """
        return self._display()


if __name__ == "__main__":
    # Create a new tree
    my_tree = Tree()

    # Add the root node
    my_tree.add_root("A")

    # Add child nodes to the root
    my_tree.add_child(my_tree.root, "B")
    my_tree.add_child(my_tree.root, "C")
    my_tree.add_child(my_tree.root, "D")
    my_tree.add_child(my_tree.root.children[0], "E")
    my_tree.add_child(my_tree.root.children[0], "F")

    # Print the tree structure
    print("Tree structure:")
    print(my_tree)
    # Output:
    # Tree structure:
    # |-- A
    #   |-- B
    #     |-- E
    #     |-- F
    #   |-- C
    #   |-- D

    # Perform breadth-first traversal
    print("Breadth-first traversal:")
    my_tree.breadth_first_traversal()
    # Output:
    # Breadth-first traversal:
    # A
    # B
    # C
    # D
    # E
    # F

    # Get the size of the tree
    tree_size = my_tree.size()
    print("Tree size:", tree_size)
    # Output:
    # Tree size: 6

    # Get the height of the tree
    tree_height = my_tree.height()
    print("Tree height:", tree_height)
    # Output:
    # Tree height: 3

    # Remove a node from the tree
    my_tree.remove_node(my_tree.root.children[0])

    # Print the tree structure after removing a node
    print("Tree structure after removing a node:")
    print(my_tree)
    # Output:
    # Tree structure after removing a node:
    # |-- A
    #   |-- C
    #   |-- D

    # Calculate the depth of a node
    node_depth = my_tree.depth(my_tree.root.children[0])
    print("Depth of node 'C':", node_depth)
    # Output:
    # Depth of node 'C': 1

    # Create a subtree rooted at a specific node
    subtree = my_tree.subtree(my_tree.root.children[0])
    print("Subtree rooted at node 'C':")
    print(subtree)
    # Output:
    # Subtree rooted at node 'C':
    # |-- C

    # Get the list of leaf nodes
    leaf_nodes = my_tree.leaves()
    leaf_values = [node.data for node in leaf_nodes]
    print("Leaf nodes:", leaf_values)
    # Output:
    # Leaf nodes: ['C', 'D']

    # Get the list of branch nodes
    branch_nodes = my_tree.branches()
    branch_values = [node.data for node in branch_nodes]
    print("Branch nodes:", branch_values)
    # Output:
    # Branch nodes: ['A']

    # Check if a node is internal
    node_c = my_tree.root.children[0]
    print(f"Is node '{node_c.data}' internal? {my_tree.is_internal_node(node_c)}")
    # Output:
    # Is node 'C' internal? False

    # Perform pre-order traversal
    print("Pre-order traversal:")
    my_tree.pre_order()
    # Output:
    # A
    # C
    # D

    # Perform in-order traversal
    print("In-order traversal:")
    my_tree.in_order()
    # Output:
    # C
    # D

    # Perform post-order traversal
    print("Post-order traversal:")
    my_tree.post_order()
    # Output:
    # C
    # D
    # A
